package com.kevin.sort;
public class QST {
    public static void main(String[] args) {
        int arr[] = {1,0,2,4,5,6,2,6,1};
        sort(arr,0,arr.length-1);
        out(arr);
    }
    private static void out(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != arr[arr.length-1]){
                System.out.print(arr[i]+",");
            }else{
                System.out.println(arr[i]);
            }
        }
    }
    public static void sort(int arr[],int start,int end){
        if (arr==null || start>end || arr.length<=1){
            return;
        }
        int mid = partition(arr,start,end);
        partition(arr,start,mid-1);
        partition(arr,mid+1,end);
    }
    private static int partition(int[] arr, int start, int end) {
        int temp = arr[start];
        while(start<end){
            while(arr[end]>temp && start<=end){
                end--;
            }
            if(start<end){
                int tmp = arr[start];
                arr[start] = arr[end];
                arr[end] = tmp;
                start++;
             }
            while(arr[start]<temp && start<=end){
                start++;
            }
            if(start<end){
                int tmp = arr[start];
                arr[start] = arr[end];
                arr[end] = tmp;
                end--;
            }
        }
        arr[start] = temp;
        return start;
    }
}



